总和|本文_Python描述LeetCode39.组合总和

篇首语：本文由编程笔记#小编为大家整理，主要介绍了Python描述 LeetCode 39. 组合总和相关的知识，希望对你有一定的参考价值。

  大家好&＃xff0c;我是亓官劼&＃xff08;qí guān jié &＃xff09;&＃xff0c;在【亓官劼】公众号、CSDN、GitHub、B站等平台分享一些技术博文&＃xff0c;主要包括前端开发、python后端开发、小程序开发、数据结构与算法、docker、Linux常用运维、NLP等相关技术博文&＃xff0c;时光荏苒&＃xff0c;未来可期&＃xff0c;加油~

  如果喜欢博主的文章可以关注博主的个人公众号【亓官劼】(qí guān jié)&＃xff0c;里面的文章更全更新更快。如果有需要找博主的话可以在公众号后台留言&＃xff0c;我会尽快回复消息.

---

本文原创为【亓官劼】&＃xff08;qí guān jié &＃xff09;&＃xff0c;请大家支持原创&＃xff0c;部分平台一直在恶意盗取博主的文章&＃xff01;&＃xff01;&＃xff01; 全部文章请关注微信公众号【亓官劼】。

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &＃xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &＃xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同&＃xff0c;则两种组合是不同的。

对于给定的输入&＃xff0c;保证和为 target 的不同组合数少于 150 个。

示例 1&＃xff1a;

输入&＃xff1a;candidates &＃61; [2,3,6,7], target &＃61; 7
输出&＃xff1a;[[2,2,3],[7]]
解释&＃xff1a;
2 和 3 可以形成一组候选&＃xff0c;2 &＃43; 2 &＃43; 3 &＃61; 7 。注意 2 可以使用多次。
7 也是一个候选&＃xff0c; 7 &＃61; 7 。
仅有这两种组合。


示例 2&＃xff1a;

输入: candidates &＃61; [2,3,5], target &＃61; 8
输出: [[2,2,2,2],[2,3,3],[3,5]]


示例 3&＃xff1a;

输入: candidates &＃61; [2], target &＃61; 1
输出: []


提示&＃xff1a;

• 1 <&＃61; candidates.length <&＃61; 30
• 1 <&＃61; candidates[i] <&＃61; 200
• candidate 中的每个元素都 互不相同
• 1 <&＃61; target <&＃61; 500

Python描述

回溯算法

class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res &＃61; []
n &＃61; len(candidates)
if target &＃61;&＃61; 0:
return []
def dfs(combine,idx):
if idx &＃61;&＃61; len(candidates):
return
# 跳过&＃xff0c;不要这个数
dfs(combine,idx&＃43;1)
# 要这个数
if sum(combine)&＃43;candidates[idx] <&＃61; target:
combine.append(candidates[idx])
if sum(combine) &＃61;&＃61; target:
res.append([_ for _ in combine])
dfs(combine,idx)
combine.pop()
dfs([],0)
return res